package top.humbleyuan.leet;

import com.sun.xml.internal.ws.policy.privateutil.PolicyUtils;
import org.junit.Test;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.AbstractQueuedSynchronizer;
import java.util.concurrent.locks.ReentrantLock;
import java.util.stream.Collectors;

/**
 * @Author HumbleYuan
 * @Date 2020/2/18 15:17
 * @Des 综合类型
 */
public class Synthesize {

    /**
     * 盛最多的水
     * 双指针：
     * 两指针从两端向中间靠，每次移动高度低的指针
     */
    @Test
    public void leet_11() {

        int[] height = {1,3,2,5,25,24,5};

        int pre = 0;
        int back = height.length - 1;
        int max = 0;
        while(pre < back) {
            int area = Math.min(height[pre], height[back]) * (back - pre);
            max = max < area ? area : max;
            if(height[pre] < height[back] ) {
                pre ++;
            }else {
                back --;
            }
        }
        System.out.println(max);

    }


    /**
     * 柱状图中最大矩阵
     * 一维最大矩阵
     * O(n2)
     */
    @Test
    public void leet_84() {
        int[] heights = {2,3};

        int max = 0;
        for(int i = 0 ;i < heights.length;i++) {
            int len = 1;
            for(int j = i - 1;j >= 0;j--) {
                if(heights[j] < heights[i]) {
                    break;
                }
                len ++;
            }

            for(int j = i + 1;j < heights.length;j++) {
                if(heights[j] < heights[i]) {
                    break;
                }
                len ++;
            }
            if(max < (len * heights[i])) {
                max = len * heights[i];
            }
        }
        System.out.println(max);
    }

    /**
     * 一维最大矩形
     * 用递增栈O(n)
     * 基本思想是：
     * 高度我们很容易知道，但是宽度怎么计算呢？宽度其实就是从当前位置向左右两边扩散。找到比自己小的或者到达边界截止。
     * 我们可以借用一个栈stack来完成这个功能。stack中的位置对于nums的值保持严格递增。
     * 利用每一次出栈操作来确定当前柱能拓宽的最大宽度
     * https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/ji-bai-liao-98de-javayong-hu-by-reedfan-9/
     */
    @Test
    public void leet_84_2() {
        Stack<Integer> stack = new Stack<>();
        int[] heights = {2,1,5,6,2,3};
        int max = 0;
        for (int i = 0; i < heights.length; i++) {
            // 第一个或者后一个较栈顶是递增
            if(stack.empty() || heights[i] > heights[stack.peek()]) {
                stack.push(i);
            }else { // 否则进行出栈
                // 一直进行出栈知道栈为空或者栈顶元素小于待入栈元素
                while (!stack.empty() && heights[stack.peek()] > heights[i]) {
                    int high = heights[stack.pop()];
                    int width;

                    // 如果栈顶为空表示左边宽即当前序号i(递增栈保证的)
                    if(stack.empty()) {
                        width = i;
                    } else { // 否则要计算右边界 - 左边界
                        width = i - stack.peek() - 1;
                    }

                    max = Math.max(max, width * high);
                }

                // **这边最后还要把需要入栈的进行入栈
                stack.push(i);
            }
        }

        // 最后一个入栈后还要进行一次处理
        while (!stack.empty()) {
            int high = heights[stack.pop()];
            int width;

            // 如果栈顶为空表示左边宽即当前序号i(递增栈保证的)
            if(stack.empty()) {
                width = heights.length;
            } else { // 否则要计算右边界 - 左边界
                width = heights.length - stack.peek() - 1;
            }

            max = Math.max(max, width * high);
        }
        System.out.println(max);
    }

    /**
     * 使用stack,但是预先push一个-1作预先设置，这样可以不考虑特殊情况
     */
    @Test
    public void leet_84_2_2() {
        /**
         * 栈的思路：
         * 1. 栈中维护一个递增的节点index;
         * 2. 遇到非递增的情况进行pop;
         * 3. 每次进行pop时计算当前pop出的index的矩形（以当前index作为高进行左右两边拓宽）;
         * 4. width = i - top - 1;
         * 由于需要找两边第一个比当前i小的index,所以存储的是index,以便计算宽度
         * 维护递增在于递增之后我们始终知道左边的瓶颈，一旦碰到非递增就知道了右边的瓶颈，就可以计算大小
         */
        int[] heights = {2,1,5,6,2,3};

        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        int maxArea = 0;

        for (int i = 0; i < heights.length; i++) {

            while(stack.peek() != -1 && heights[stack.peek()] > heights[i]) {
                int index = stack.pop();

                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, width * heights[index]);
            }

            stack.push(i);
        }

        // 最后会剩下一个递增的stack,进行stack非空处理
        while(stack.peek() != -1) {
            int index = stack.pop();

            int width = heights.length - stack.peek() - 1;
            maxArea = Math.max(maxArea, width * heights[index]);
        }

        System.out.println(maxArea);
    }

    /**
     * 分治法
     */
    @Test
    public void leet_84_3() {
        /**
         * 最大矩形出现的三种情况：
         * 1. 以最矮矩形为高的矩形
         * 2. 最矮矩形左边的部分中有最大
         * 3. 最矮矩形右边的部分中有最大
         * 其中2，3中找最大依然按照这种方式
         */

        int[] heights = {2,1,5,6,2,3};

        int max = divide(heights, 0);
        System.out.println(max);
    }

    public int divide(int[] heights, int maxArea) {
        if(heights == null || heights.length == 0) {
            return maxArea;
        }

        int minHeight = Integer.MAX_VALUE;
        int minIndex = -1;

        for (int i = 0; i < heights.length; i++) {
            if(heights[i] < minHeight) {
                minIndex = i;
                minHeight = heights[i];
            }
        }

        maxArea = Math.max(maxArea, minHeight * heights.length);

        // 左右开弓
        int[] left = Arrays.copyOf(heights, minIndex);
        int[] right = Arrays.copyOfRange(heights, minIndex + 1, heights.length);

        maxArea = Math.max(maxArea, Math.max(divide(left, maxArea), divide(right, maxArea)));

        return maxArea;

    }


    /**
     * 字符串全排列
     */
    @Test
    public void leet_mianshi38() {
        String str = "123";
        ArrayList<String>  list = new ArrayList<>();

        fullPermutation(0, str.toCharArray(), list);

        System.out.println(list);
    }

    /**
     * j表示的是当前需要全排列串的第一个
     * 即核心思想：选取一个当做头，其余全排列
     * @param j
     * @param str
     * @param list
     */
    public void fullPermutation(int j, char[] str, ArrayList<String> list) {
        // 递归退出
        if(j == str.length - 1) {
            // 当前str中为一种全排列
            String s = String.valueOf(str);

            // 去重
            if(!list.contains(s)) {
                list.add(s);
            }
            return;
        }

        // 从j开始，选取一个为头，后面进行全排列
        for (int i = j; i < str.length; i++) {
            swap(str, i, j);
            // 后面进行全排列,
            fullPermutation(j+1,str,list);
            // 回到上一个状态
            swap(str, i, j);
        }

        int[] nums = {1,2,3};
        String.valueOf(nums);

    }

    // 这里用交换选取头
    public void swap(char[] str, int i, int j) {
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }


    /**
     * 字符串全排列：
     * 利用剪枝 + 回溯
     */
    @Test
    public void leet_mianshi38_2() {
        String s = "abc";
        // 利用回溯 + 剪枝
        ArrayList<String> res = new ArrayList<>();
        char[] c = s.toCharArray();
        Arrays.sort(c);

        String cur = "";
        dfs(res, cur, c, new boolean[c.length]);
        System.out.println(res);
    }



    public void dfs(ArrayList<String> res, String cur, char[] cha, boolean[] vistied) {
        if(cur.length() == cha.length) {
            res.add(new String(cur));
            return;
        }

        for(int i = 0 ; i < cha.length ; i++) {
            if(vistied[i]) {
                continue;
            }

            if(i > 0 && cha[i] == cha[i - 1] && !vistied[i - 1]) {
                continue;
            }

            cur += cha[i];
            vistied[i] = true;
            dfs(res, cur, cha, vistied);
            cur = cur.substring(0,cur.length() - 1);
            vistied[i] = false;
        }
    }


    /**
     * 最长有效括号
     * // dp解法未写
     */
    @Test
    public void leet_32() {
        String s = "(())(";

        if(s == null || s.length() == 0) {
            System.out.println(0);
        }

        /**
         打断条件：stack is empty && s[i] == ')'
         **/

        int i = 0;
        int maxCount = 0;
        Stack<Integer> stack = new Stack<>();

        // -1进栈,做全体规则的计算
        stack.push(-1);
        while(i < s.length()) {
            if(s.charAt(i) == '(') {
                stack.push(i);
            } else {
                // 先弹出
                stack.pop();

                // 计算增加大小
                if(stack.empty()) {
                    // 空则中断,压入新起点做计算。相当于-1
                    stack.push(i);
                } else {
                    maxCount = Math.max(maxCount, i - stack.peek());
                }
            }

            i++;
        }

        System.out.println(maxCount);
    }

    /**
     * 最长无重复子串
     */
    @Test
    public void leet_3() {
        String s = "bacadef";
        String s1 = s;
        int maxLength = 0;
        Set<Character> set = new HashSet<>();
        int i=0,  j=0;
        while(i < s.length()&&j<s.length()) {
            if(!set.contains(s1.charAt(j))){
                set.add(s1.charAt(j++));
                maxLength = Math.max(maxLength,set.size());
            }
            else
                set.remove(s1.charAt(i++));
        }
        System.out.println(maxLength);
    }

    /**
     * 组合总和
     * 回溯剪枝
     * leet_39
     */
    List<List<Integer>> res_39 = new ArrayList<>();
    @Test
    public void leet_39() {
        int[] candidates = {2,3,6,7};
        int target = 7;
        Arrays.sort(candidates);

        dfs(0, new ArrayList<>(), target, candidates);
        System.out.println(res_39);
    }

    public void dfs(int sum, ArrayList<Integer> list,int target,int[] candidates) {
        if(sum == target) {
            res_39.add(new ArrayList<>(list));
            return;
        }

        for(int i = 0;i < candidates.length;i++) {
            sum += candidates[i];
            // 剪枝
            if(sum > target) {
                sum -= candidates[i];
                continue;
            }

            list.add(candidates[i]);
            int[] newInt = Arrays.copyOfRange(candidates, i, candidates.length);

            dfs(sum, list, target, newInt);

            //回溯
            sum -= candidates[i];
            list.remove(list.size() - 1);
        }
    }


    /**
     * 电话号码回溯 leet_17
     * @param args
     */
    static Map<Character, String> phone = new HashMap<Character, String>() {{
        put('2', "abc");
        put('3', "def");
        put('4', "ghi");
        put('5', "jkl");
        put('6', "mno");
        put('7', "pqrs");
        put('8', "tuv");
        put('9', "wxyz");
    }};

    static List<String> res = new ArrayList<>();

    public static void leet_17(String s, String curStr) {
        if(s.length() == 0) {
            res.add(curStr);
            return ;
        }

        /**
         * 以每个数字的所有字母为循环，依次回溯
         */
        // 获取当前数字
        Character c = s.charAt(0);
        String letters = phone.get(c);

        for (int i = 0; i < letters.length(); i++) {
            curStr += letters.charAt(i);

            // 深度遍历
            leet_17(s.substring(1), curStr);

            // 回溯
            curStr = curStr.substring(0, curStr.length()-1);
        }
    }

    /**
     * 阶乘后的0
     */
    public static void leet_172(){
        /**
         1. 5,25,125...分别是1,2,3...个5,
         2. n / 5 + n / 25 + n / 125...(因为n / 5包含后面所有5倍数的l个，后面依次类推)
         **/
        int n = 7;
        int res = 0;
        while(n >= 5) {
            res += n / 5;

            // 这里n/5相当于上面的除数乘以5
            n /= 5;
        }

        System.out.println(res);
    }


    /**
     * 找重复数，二分法
     */
    @Test
    public void leet_287() {
        int[] nums = {1,6,2,3,5,6,4};

        int same = findSame(nums, 1, nums.length);
        System.out.println(same);
    }

    public static int findSame(int[] nums, int begin, int end) {
        if(begin == end) {
            return begin;
        }

        int mid = (begin + end) >> 1;


        // 这里注意取base，得到>= base的数count是否> mid
        // 这里不能写成(mid - 1, mid + 1)的二分，应为mid也有可能是
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] <= mid) {
                count++;
            }
        }

        if(count > mid) {
            end = mid;
        } else {
            begin = mid + 1;
        }

        return findSame(nums, begin, end);
    }


    public static void main(String[] args) {

        System.out.println('a' - 'a');
        //电话号码表示字符串
//        String s = "345";
//        leet_17(s, "");
//        System.out.println(res);



    }

}


